package datastructure.book.dp._2_linear_pre_section.single.all;

import org.junit.jupiter.api.Test;

public class _10_Solution {

    @Test
    public void test(){
        int[] arr = {1,3,1,3,100};
        System.out.println(rob(arr));
    }

    public int rob(int[] nums) {
        if (nums.length < 2) {
            return nums[0];
        }
        if (nums.length < 3) {
            return Math.max(nums[0],nums[1]);
        }
        return Math.max(robRange(nums,0,nums.length-2),robRange(nums,1,nums.length-1));
    }

    private int robRange(int[] nums, int start, int end) {
        if (end - start < 2) {
            return Math.max(nums[start],nums[end]);
        }
        int[] dp = new int[end - start +1];
        dp[0] = nums[start];dp[1] = Math.max(nums[start+1],nums[start]);
        for (int i = start+2; i <= end; i++) {
            dp[i-start] = Math.max(dp[i-start-1],dp[i-start-2]+nums[i]);
        }
        return dp[dp.length-1];
    }
}
